package binary_search;

/**题目：二分搜索
 * 给定一个递增的数组，寻找某个值的下标位置
 * @Author Gavin
 * @date 2022.01.02 10:05
 */
public class array_1 {
    //Time:O(log(n)) Space:O(1)
    public static int solution(int[] nums ,int target){
        if(nums.length==0)return -1;
        int low=0,high=nums.length-1;
        while (low<=high){
            /**
             *注意，这里不使用（low+high）/2是因为怕内存溢出，
             * 有可能low的值和high的值都非常大了，然后两个相加就超过
             * int的最大值了
             */
            int mid=low+(high-low)/2;
            if(target<nums[mid])high=mid-1;
            else if (target>nums[mid])low=mid+1;
            else return mid;
        }
        return -1;
    }
}
